package com.lyf.alg.practice.newcoder.top101.grady;

import java.util.*;

class Node{
    public int start,end;
    public Node(int start,int end){
        this.start = start;
        this.end = end;
    }
}
public class Solution {

    public static void main(String[] args) {
        int[][] arr = new int[2][2];
        arr[0][0]=1;
        arr[0][1]=2;
        arr[1][0]=2;
        arr[1][1]=3;
           int rs=new Solution().minmumNumberOfHost(2,arr);
        System.out.println(rs);

//        Set<Node> set = new HashSet<>();
//        set.add(new Node(1,2));
//        set.add(new Node(2,3));
//        Iterator<Node> iterator = set.iterator();
//        System.out.println(iterator.next().start+"::"+iterator.next().start);

    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算成功举办活动需要多少名主持人
     * @param n int整型 有n个活动
     * @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
     * @return int整型
     */



    public int minmumNumberOfHost (int n, int[][] startEnd) {
        // write code here

        // 贪心算法
        // 思路：遍历选取set{}能够一次主持完并标记，直到set.size()==0

//         int s = 0;// 已选取的活动
//         int flag[n];// 标记1-n活动（下标0-n-1）是否选取，默认为0
//         // 每次若都从 0开始选则 时间复杂度为 n + .. n^n

        // 转  Set -- ，move --  n + ... 1   →  n^2

        int c=0;

        Set<Node> set = new HashSet<>();

        for(int i=0;i<startEnd.length;i++){
            set.add(new Node(startEnd[i][0],startEnd[i][1]));
        }

        while(!set.isEmpty()){
            // 开始进行选取
            c++;
            //Node firstNode = set.indexOf(0);
            Iterator<Node> iterator=set.iterator();
            // 必有--next--
            Node firstNode = iterator.next();

            int start = firstNode.start;
            int end = firstNode.end;

            iterator.remove();

            while(iterator.hasNext()){
                Node tmp = iterator.next();
//                if(tmp.start>=end){
//                    iterator.remove();
//                    end = tmp.start;
//                }
                if(tmp.start>=end){
                    iterator.remove();
                    end = tmp.end;
                }else if(tmp.end<=start){
                    iterator.remove();
                    start = tmp.start;
                }

            }

        }

        return c;
    }
}